class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        // 1.将链表从中间分开
        ListNode* fast = head, *slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2.将后半部分逆序
        ListNode* newhead1 = new ListNode;
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead1->next;
            newhead1->next= cur;
            cur = next;
        }
        // 3.一前一后合并
        ListNode* newhead2 = new ListNode;
        ListNode* tail = newhead2, *cur1 = head, *cur2 = newhead1->next;
        while (cur1)
        {
            tail->next = cur1;
            cur1 = cur1->next;
            tail = tail->next;
            if (cur2)
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }
        delete newhead1;
        delete newhead2;
    }
};
    